“Лiнгвiстичне забезпечення САПР”
1.(184) Записати граматику, по якiй генеруються довiльнi рядки (включаючи порожнi) по алфавiту {0,1}.
Граматика описується наступною четівркою Vn - множина нетермінальних символів, Vt - множина термінальних символів,S - початковий символ,P - множина правил підстановки.
Множина термінальних символів Vn={0, 1, e}, де е - пустий ланцюжок
Множина нетермінальних символів Vt={A, S}, де S - початковий символ
Множина правил підстановки Р:
S ->A; A->e; A->0A; A->A0; A->1A; A->A1;
або
S->A; A-> e | 0A | A0 | 1A | A1
Граматика яка описується такою четвіркою генерує довільні рядки по алфавіту {0, 1}
2. (185) Побудувати автомат для розпiзнавання ланцюжкiв, якi можуть знаходитися пiсля слова INTEGER в операторах специфiкацiї формату.
Ролі, які зустрічаються в наступній задачі можуть бути описані так:
2 - ім'я змінної, описаної як INTEGER
3 - ліва дужка
4 - ціла стала, яка визначає розмірність
5 - кома, яка розділяє розмірності
6 - змінна, яка визначає змінну розмірність
7 - права дужка
8 - кома, яка розділяє об'єкти, описані як цілі
Після того, коли всі ролі позначені автомат може бути побудований по такому алгоритму:
Крок 1 Ввести початковий стан і стан помилки
Крок 2 Ввести стан для кожної ролі
Крок 3 Помістити в таблицю переходи з одного стану в інший, якщо відповідні ролі можуть поступати одна за одною
Крок 4 Поповнити таблицю переходами в стан помилки
Крок 5 Вибрати в якості допускаючих ті стани, ролі яких з'являються в кінці допускаючих ланцюжків
Початковий стан - 1, Стан помилки - Е
* - Допускаючі стани - 2 і 7
3.(186) Описати автомат i написати ланцюжки, якi допускає i якi вiдкидає розпiзнавальний автомат, зображений на рисунку:
Скінченний автомат описується наступним чином:
EMBED Equation.3 , де Q - скінченна множина станів, S - початковий стан, EMBED Equation.3 - множина переходів, EMBED Equation.3 - скінченний вхідний алфавіт, F - множина заключних станів
У даному випадку: Q={1, 2, E}, S=1, EMBED Equation.3 ={A,B}, F={1}
Множина переходів
EMBED Equation.3 (1,A)=1 EMBED Equation.3 (1,B)=2; EMBED Equation.3 (2,A)=E; EMBED Equation.3 (2,B)=1; EMBED Equation.3 (E,A)=E; EMBED Equation.3 (E,B)=E
A,B
A
B
B
A
1
2
E
Можливі наступні варіанти ланцюжків, які допускає даний автомат: Аn, АnВВ , після кожної послідовності символів А повинно йти два символи В або ланцюжок має закінчитись.
4. (187) Побудувати кiнцевий розпiзнавач для множин ланцюжкiв з нулiв i одиниць з кiнцевим маркером, при цьому виявляти допустимi i недопустимi ланцюжки необхiдно якнайшвидше: - кiлькiсть одиниць парна, а кiлькiсть нулiв непарна
Введемо наступні стани:
А - кількість нулів парна, кількість одиниць парна;
В - кількість нулів непарна, кількість одиниць парна;
С - кількість нулів парна, кількість одиниць непарна;
D - кількість нулів непарна, кількість одиниць непарна;
Допускаючим станом є стан В.
Таблиця переходів виглядає наступним чином:
5. (188) Побудувати кiнцевий розпiзнавач для множин ланцюжкiв з нулiв i одиниць з кiнцевим маркером, при цьому виявляти допустимi i недопустимi ланцюжки необхiдно якнайшвидше: - мiж одиницями в ланцюжку парна кiлькiсть нулiв
Множина станів для такого розпізнавача: S={S1,S2}, множина магазиннних символів: {С,Z}. Вхідний алфавіт: {0, 1, -| }. Множина переходів описується наступними таблицями:
Для стану S1:
Для стану S2:
6. (189) Побудувати кiнцевий розпiзнавач для множин ланцюжкiв з нулiв i одиниць з кiнцевим маркером, при цьому виявляти допустимi i недопустимi ланцюжки необхiдно якнайшвидше: - пiсля кожної пари одиниць знаходиться нуль
Множина станів для такого розпізнавача: S={S1,S2}, множина магазиннних символів: {С,Z}. Вхідний алфавіт: {0, 1, -| }. Множина переходів описується наступними таблицями:
Для стану S1:
Для стану S2:
7. (190) Побудувати кiнцевий розпiзнавач для множин ланцюжкiв з нулiв i одиниць з кiнцевим маркером, при цьом...
